package solution.liuyu2783.offer;


/**
 * 剑指 Offer 16. 数值的整数次方
 *
 */
public class Q16_PowCalculate_M {

	public static void main(String[] args) {
		System.out.println(myPow(2,-2147483648));
	}
	
	/**
	 * 思路：
	 * 二分法：x^n = x^(n/2)*x^(n/2) = x^2^n/2 = (x*x)^n/2
	 * 当 n 为偶数：x^n = (x*x)^n/2
	 * 当 n 为技术：x^n = x * (x*x)^n/2
	 */
	public static double myPow(double d, int p) {
		if(p == 0) {
			return 1;
		}
		
		if(p < 0) {//负数
			//如果当n=Integer.MIN_VALUE的时候，Integer.MIN_VALUE的相反数还是他自己，所以会一直调用，直到最后出现堆栈溢出异常。
			//所以有一种方式就是把1/x提取出来一个
			p = -p;
			return 1/d * myPow (1/d, p -1);
		}
		if(p % 2 == 0) { //偶数
			return myPow(d*d, p/2);
		}else{ //基数
			return d * myPow(d*d, p/2);
		}
	}
}
